home *** CD-ROM | disk | FTP | other *** search
/ MacFormat 1995 July / macformat-026.iso / mac / Shareware City / Developers / berkeleydb1.73 / Berkeley_db / hash / hash_func.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-07-27  |  4.7 KB  |  196 lines  |  [TEXT/MPS ]
  1. /*-
  2.  * Copyright (c) 1990, 1993
  3.  *    The Regents of the University of California.  All rights reserved.
  4.  *
  5.  * This code is derived from software contributed to Berkeley by
  6.  * Margo Seltzer.
  7.  *
  8.  * Redistribution and use in source and binary forms, with or without
  9.  * modification, are permitted provided that the following conditions
  10.  * are met:
  11.  * 1. Redistributions of source code must retain the above copyright
  12.  *    notice, this list of conditions and the following disclaimer.
  13.  * 2. Redistributions in binary form must reproduce the above copyright
  14.  *    notice, this list of conditions and the following disclaimer in the
  15.  *    documentation and/or other materials provided with the distribution.
  16.  * 3. All advertising materials mentioning features or use of this software
  17.  *    must display the following acknowledgement:
  18.  *    This product includes software developed by the University of
  19.  *    California, Berkeley and its contributors.
  20.  * 4. Neither the name of the University nor the names of its contributors
  21.  *    may be used to endorse or promote products derived from this software
  22.  *    without specific prior written permission.
  23.  *
  24.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34.  * SUCH DAMAGE.
  35.  */
  36.  
  37. #if defined(LIBC_SCCS) && !defined(lint)
  38. static char sccsid[] = "@(#)hash_func.c    8.1 (Berkeley) 6/4/93";
  39. #endif /* LIBC_SCCS and not lint */
  40.  
  41. #if defined(macintosh) && (defined(powerc) || defined(__powerc))
  42. #include "OurMalloc.h"
  43. #endif
  44.  
  45. #include <sys/types.h>
  46.  
  47. #include <db.h>
  48. #include "hash.h"
  49. #include "page.h"
  50. #include "extern.h"
  51.  
  52. static int hash1 __P((u_char *, int));
  53. static int hash2 __P((u_char *, int));
  54. static int hash3 __P((u_char *, int));
  55. static int hash4 __P((u_char *, int));
  56.  
  57. /* Global default hash function */
  58. int (*__default_hash) __P((u_char *, int)) = hash4;
  59.  
  60. /******************************* HASH FUNCTIONS **************************/
  61. /*
  62.  * Assume that we've already split the bucket to which this key hashes,
  63.  * calculate that bucket, and check that in fact we did already split it.
  64.  *
  65.  * This came from ejb's hsearch.
  66.  */
  67.  
  68. #define PRIME1        37
  69. #define PRIME2        1048583
  70.  
  71. static int
  72. hash1(key, len)
  73.     register u_char *key;
  74.     register int len;
  75. {
  76.     register int h;
  77.  
  78.     h = 0;
  79.     /* Convert string to integer */
  80.     while (len--)
  81.         h = h * PRIME1 ^ (*key++ - ' ');
  82.     h %= PRIME2;
  83.     return (h);
  84. }
  85.  
  86. /*
  87.  * Phong's linear congruential hash
  88.  */
  89. #define dcharhash(h, c)    ((h) = 0x63c63cd9*(h) + 0x9c39c33d + (c))
  90.  
  91. static int
  92. hash2(key, len)
  93.     register u_char *key;
  94.     int len;
  95. {
  96.     register u_char *e, c;
  97.     register int h;
  98.  
  99.     e = key + len;
  100.     for (h = 0; key != e;) {
  101.         c = *key++;
  102.         if (!c && key > e)
  103.             break;
  104.         dcharhash(h, c);
  105.     }
  106.     return (h);
  107. }
  108.  
  109. /*
  110.  * This is INCREDIBLY ugly, but fast.  We break the string up into 8 byte
  111.  * units.  On the first time through the loop we get the "leftover bytes"
  112.  * (strlen % 8).  On every other iteration, we perform 8 HASHC's so we handle
  113.  * all 8 bytes.  Essentially, this saves us 7 cmp & branch instructions.  If
  114.  * this routine is heavily used enough, it's worth the ugly coding.
  115.  *
  116.  * OZ's original sdbm hash
  117.  */
  118. static int
  119. hash3(key, len)
  120.     register u_char *key;
  121.     register int len;
  122. {
  123.     register int n, loop;
  124.  
  125. #define HASHC   n = *key++ + 65599 * n
  126.  
  127.     n = 0;
  128.     if (len > 0) {
  129.         loop = (len + 8 - 1) >> 3;
  130.  
  131.         switch (len & (8 - 1)) {
  132.         case 0:
  133.             do {    /* All fall throughs */
  134.                 HASHC;
  135.         case 7:
  136.                 HASHC;
  137.         case 6:
  138.                 HASHC;
  139.         case 5:
  140.                 HASHC;
  141.         case 4:
  142.                 HASHC;
  143.         case 3:
  144.                 HASHC;
  145.         case 2:
  146.                 HASHC;
  147.         case 1:
  148.                 HASHC;
  149.             } while (--loop);
  150.         }
  151.  
  152.     }
  153.     return (n);
  154. }
  155.  
  156. /* Hash function from Chris Torek. */
  157. static int
  158. hash4(key, len)
  159.     register u_char *key;
  160.     register int len;
  161. {
  162.     register int h, loop;
  163.  
  164. #define HASH4a   h = (h << 5) - h + *key++;
  165. #define HASH4b   h = (h << 5) + h + *key++;
  166. #define HASH4 HASH4b
  167.  
  168.     h = 0;
  169.     if (len > 0) {
  170.         loop = (len + 8 - 1) >> 3;
  171.  
  172.         switch (len & (8 - 1)) {
  173.         case 0:
  174.             do {    /* All fall throughs */
  175.                 HASH4;
  176.         case 7:
  177.                 HASH4;
  178.         case 6:
  179.                 HASH4;
  180.         case 5:
  181.                 HASH4;
  182.         case 4:
  183.                 HASH4;
  184.         case 3:
  185.                 HASH4;
  186.         case 2:
  187.                 HASH4;
  188.         case 1:
  189.                 HASH4;
  190.             } while (--loop);
  191.         }
  192.  
  193.     }
  194.     return (h);
  195. }
  196.